class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        //dp[i][j]代表s1以i位置为结尾的子序列中和s2以j位置为结尾的子序列中最长的公共子序列的长度为多少
        //然后就是状态转移方程的书写了
        int len1 = s1.size();
        int len2 = s2.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        s1 = "-"+s1;
        s2 = "-"+s2;
        for(int i = 1;i<=len1;i++)
        {
            for(int j = 1;j<=len2;j++)
            {
                if(s1[i] == s2[j])
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else
                {
                    //否则就去s1的i-1位置和j去进行判断，或者是s2的j-1位置和i进行判断
                    //选出最大的值
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
};